package 中等.贪心思想;

/**
 * 给你一个整数数组 nums，每次 操作 会从中选择一个元素并 将该元素的值减少 1。
 * 如果符合下列情况之一，则数组 A 就是 锯齿数组：
 * 每个偶数索引对应的元素都大于相邻的元素，即 A[0] > A[1] < A[2] > A[3] < A[4] > ...
 * 或者，每个奇数索引对应的元素都大于相邻的元素，即 A[0] < A[1] > A[2] < A[3] > A[4] < ...
 * 返回将数组 nums 转换为锯齿数组所需的最小操作次数。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/decrease-elements-to-make-array-zigzag
 */
public class 递减元素使数组呈锯齿状_1144 {

    public static void main(String[] args) {

        System.out.println(movesToMakeZigzag(new int[]{1, 2, 3}));

    }

    /**
     * 贪心思想+分类讨论+逆向思维
     * 1，当前元素大于左右两侧，可以转换为，当前元素需要小于左右两侧元素
     * 那么当前元素的最大值为 Math.min(left-1,right-1)，也就是说当前
     * 元素如果 > Math.min(left-1,right-1)，那么需要操作 nums[i] - Math.min(left-1,right-1)
     * 次数，不存在将左右两边 + 1 的做法，因为每次操作规定了 - 1
     * 2，两种情况，每个奇数位均小于左右两侧元素，或者每个偶数位小于
     * 左右两侧元素
     */
    public static int movesToMakeZigzag(int[] nums) {
        int oddSum = 0, evenSum = 0;

        for (int i = 0; i < nums.length; i += 2) {
            int need = Integer.MAX_VALUE;
            if (i - 1 >= 0) {
                need = Math.min(need, nums[i - 1] - 1);
            }
            if (i + 1 < nums.length) {
                need = Math.min(need, nums[i + 1] - 1);
            }
            oddSum += Math.max(0, nums[i] - need);
        }

        for (int i = 1; i < nums.length; i += 2) {
            int need = Integer.MAX_VALUE;
            if (i - 1 >= 0) {
                need = Math.min(need, nums[i - 1] - 1);
            }
            if (i + 1 < nums.length) {
                need = Math.min(need, nums[i + 1] - 1);
            }
            evenSum += Math.max(0, nums[i] - need);
        }

        return Math.min(oddSum, evenSum);
    }

}
